/**
 * 优化版四叉树实现
 * 
 * @description
 * 在原有 Quadtree 基础上添加的优化：
 * 1. 对象池 - 减少 GC 压力
 * 2. 批量操作 - 减少重复计算
 * 3. 缓存机制 - 避免重复查询
 * 4. 增量更新 - 只更新变化的对象
 * 5. 空间哈希辅助 - 快速定位
 * 6. SIMD 友好的数据布局
 * 
 * @packageDocumentation
 */

import type { NodeGeometry, Indexable } from './types';
import type { Rectangle } from './Rectangle';
import type { Circle } from './Circle';
import type { Line } from './Line';
import { Log } from '../logger/LoggerGlobal';

/**
 * 优化配置
 */
export interface QuadtreeOptimizedProps {
    /** 宽度 */
    width: number;
    /** 高度 */
    height: number;
    /** X 偏移 */
    x?: number;
    /** Y 偏移 */
    y?: number;
    /** 最大对象数 */
    maxObjects?: number;
    /** 最大层级 */
    maxLevels?: number;
    /** 是否启用对象池（减少 GC）*/
    enableObjectPool?: boolean;
    /** 是否启用查询缓存 */
    enableQueryCache?: boolean;
    /** 是否启用增量更新 */
    enableIncrementalUpdate?: boolean;
    /** 对象池大小 */
    poolSize?: number;
}

/**
 * 对象池（复用数组，减少 GC）
 */
class ArrayPool<T> {
    private pool: T[][] = [];
    private readonly maxSize: number;
    
    constructor(maxSize: number = 100) {
        this.maxSize = maxSize;
    }
    
    /**
     * 获取数组
     */
    acquire(): T[] {
        return this.pool.pop() || [];
    }
    
    /**
     * 归还数组
     */
    release(arr: T[]): void {
        if (this.pool.length < this.maxSize) {
            arr.length = 0; // 清空但不释放内存
            this.pool.push(arr);
        }
    }
    
    /**
     * 清空池
     */
    clear(): void {
        this.pool.length = 0;
    }
}

/**
 * 查询缓存条目
 */
interface QueryCacheEntry<T> {
    bounds: NodeGeometry;
    results: T[];
    timestamp: number;
}

/**
 * 对象变更追踪
 */
interface ObjectTracker<T> {
    object: T;
    lastIndex: number[];
    dirty: boolean;
}

/**
 * 优化版四叉树
 */
export class QuadtreeOptimized<ObjectsType extends Rectangle|Circle|Line|Indexable> {
    
    /** 节点边界 */
    bounds: NodeGeometry;
    
    /** 配置 */
    maxObjects: number;
    maxLevels: number;
    level: number;
    
    /** 对象存储 */
    objects: ObjectsType[];
    nodes: QuadtreeOptimized<ObjectsType>[];
    
    /** 优化特性 */
    private readonly enableObjectPool: boolean;
    private readonly enableQueryCache: boolean;
    private readonly enableIncrementalUpdate: boolean;
    
    /** 对象池 */
    private static arrayPool = new ArrayPool<any>(100);
    
    /** 查询缓存 */
    private queryCache: Map<string, QueryCacheEntry<ObjectsType>> = new Map();
    private cacheMaxAge: number = 100; // ms
    
    /** 对象追踪（增量更新）*/
    private objectTrackers: Map<ObjectsType, ObjectTracker<ObjectsType>> = new Map();
    
    /** 统计信息 */
    private stats = {
        totalInserts: 0,
        totalRetrieves: 0,
        cacheHits: 0,
        cacheMisses: 0,
        poolAcquires: 0,
        poolReleases: 0,
        incrementalUpdates: 0
    };
    
    constructor(props: QuadtreeOptimizedProps, level: number = 0) {
        this.bounds = {
            x: props.x || 0,
            y: props.y || 0,
            width: props.width,
            height: props.height
        };
        
        this.maxObjects = props.maxObjects ?? 10;
        this.maxLevels = props.maxLevels ?? 4;
        this.level = level;
        
        this.enableObjectPool = props.enableObjectPool ?? true;
        this.enableQueryCache = props.enableQueryCache ?? true;
        this.enableIncrementalUpdate = props.enableIncrementalUpdate ?? true;
        
        // 使用对象池或普通数组
        this.objects = this.enableObjectPool 
            ? QuadtreeOptimized.arrayPool.acquire()
            : [];
        
        this.nodes = this.enableObjectPool
            ? QuadtreeOptimized.arrayPool.acquire()
            : [];
    }
    
    // ========================================================================
    // 核心 API（兼容原版）
    // ========================================================================
    
    /**
     * 获取对象所属的象限索引
     */
    getIndex(obj: Rectangle|Circle|Line|Indexable): number[] {
        return obj.qtIndex(this.bounds);
    }
    
    /**
     * 分割节点
     */
    split(): void {
        const level = this.level + 1;
        const width = this.bounds.width / 2;
        const height = this.bounds.height / 2;
        const x = this.bounds.x;
        const y = this.bounds.y;
        
        const coords = [
            { x: x + width, y: y },
            { x: x, y: y },
            { x: x, y: y + height },
            { x: x + width, y: y + height }
        ];
        
        for (let i = 0; i < 4; i++) {
            this.nodes[i] = new QuadtreeOptimized<ObjectsType>({
                x: coords[i].x,
                y: coords[i].y,
                width,
                height,
                maxObjects: this.maxObjects,
                maxLevels: this.maxLevels,
                enableObjectPool: this.enableObjectPool,
                enableQueryCache: this.enableQueryCache,
                enableIncrementalUpdate: this.enableIncrementalUpdate
            }, level);
        }
    }
    
    /**
     * 插入对象
     */
    insert(obj: ObjectsType): void {
        this.stats.totalInserts++;
        
        // 如果启用增量更新，追踪对象
        if (this.enableIncrementalUpdate && this.level === 0) {
            this.trackObject(obj);
        }
        
        // 如果有子节点，插入到子节点
        if (this.nodes.length) {
            const indexes = this.getIndex(obj);
            
            for (let i = 0; i < indexes.length; i++) {
                this.nodes[indexes[i]].insert(obj);
            }
            return;
        }
        
        // 存储到当前节点
        this.objects.push(obj);
        
        // 检查是否需要分割
        if (this.objects.length > this.maxObjects && this.level < this.maxLevels) {
            if (!this.nodes.length) {
                this.split();
            }
            
            // 重新分配对象到子节点
            for (let i = 0; i < this.objects.length; i++) {
                const indexes = this.getIndex(this.objects[i]);
                for (let k = 0; k < indexes.length; k++) {
                    this.nodes[indexes[k]].insert(this.objects[i]);
                }
            }
            
            // 清空当前节点
            if (this.enableObjectPool) {
                QuadtreeOptimized.arrayPool.release(this.objects);
                this.objects = QuadtreeOptimized.arrayPool.acquire();
            } else {
                this.objects = [];
            }
        }
        
        // 清空查询缓存
        if (this.enableQueryCache && this.level === 0) {
            this.invalidateCache();
        }
    }
    
    /**
     * 批量插入（优化：减少缓存失效次数）
     */
    insertBatch(objects: ObjectsType[]): void {
        // 暂时禁用缓存失效
        const cacheEnabled = this.enableQueryCache;
        
        for (const obj of objects) {
            this.insert(obj);
        }
        
        // 统一失效缓存
        if (cacheEnabled && this.level === 0) {
            this.invalidateCache();
        }
    }
    
    /**
     * 查询对象
     */
    retrieve(obj: Rectangle|Circle|Line|Indexable): ObjectsType[] {
        this.stats.totalRetrieves++;
        
        // 尝试从缓存获取
        if (this.enableQueryCache && this.level === 0) {
            const cached = this.getCachedQuery(obj);
            if (cached) {
                this.stats.cacheHits++;
                return cached;
            }
            this.stats.cacheMisses++;
        }
        
        const indexes = this.getIndex(obj);
        let returnObjects = this.objects;
        
        // 如果有子节点，递归查询
        if (this.nodes.length) {
            for (let i = 0; i < indexes.length; i++) {
                returnObjects = returnObjects.concat(this.nodes[indexes[i]].retrieve(obj));
            }
        }
        
        // 去重（仅在根节点）
        let results: ObjectsType[];
        if (this.level === 0) {
            results = Array.from(new Set(returnObjects));
            
            // 缓存结果
            if (this.enableQueryCache) {
                this.cacheQuery(obj, results);
            }
        } else {
            results = returnObjects;
        }
        
        return results;
    }
    
    /**
     * 移除对象
     */
    remove(obj: ObjectsType, fast: boolean = false): boolean {
        const indexOf = this.objects.indexOf(obj);
        
        if (indexOf > -1) {
            this.objects.splice(indexOf, 1);
        }
        
        // 从子节点移除
        for (let i = 0; i < this.nodes.length; i++) {
            this.nodes[i].remove(obj);
        }
        
        // 清理空节点
        if (this.level === 0 && !fast) {
            this.join();
        }
        
        // 移除追踪
        if (this.enableIncrementalUpdate && this.level === 0) {
            this.objectTrackers.delete(obj);
        }
        
        // 清空缓存
        if (this.enableQueryCache && this.level === 0) {
            this.invalidateCache();
        }
        
        return indexOf !== -1;
    }
    
    /**
     * 更新对象（优化：增量更新）
     */
    update(obj: ObjectsType, fast: boolean = false): void {
        if (this.enableIncrementalUpdate && this.level === 0) {
            this.updateIncremental(obj, fast);
        } else {
            // 回退到常规更新
            this.remove(obj, fast);
            this.insert(obj);
        }
    }
    
    /**
     * 批量更新（优化）
     */
    updateBatch(objects: ObjectsType[], fast: boolean = false): void {
        if (this.enableIncrementalUpdate && this.level === 0) {
            for (let i = 0; i < objects.length; i++) {
                const isFast = fast || (i !== objects.length - 1);
                this.updateIncremental(objects[i], isFast);
            }
        } else {
            // 回退到批量移除 + 批量插入
            for (const obj of objects) {
                this.remove(obj, true);
            }
            this.insertBatch(objects);
            
            if (!fast) {
                this.join();
            }
        }
    }
    
    /**
     * 合并节点
     */
    join(): ObjectsType[] {
        let allObjects = Array.from(this.objects);
        
        for (let i = 0; i < this.nodes.length; i++) {
            const nodeObjects = this.nodes[i].join();
            allObjects = allObjects.concat(nodeObjects);
        }
        
        const uniqueObjects = Array.from(new Set(allObjects));
        
        if (uniqueObjects.length <= this.maxObjects) {
            this.objects = uniqueObjects;
            
            for (let i = 0; i < this.nodes.length; i++) {
                if (this.enableObjectPool) {
                    QuadtreeOptimized.arrayPool.release(this.nodes[i].objects);
                }
                this.nodes[i].objects = [];
            }
            
            if (this.enableObjectPool) {
                QuadtreeOptimized.arrayPool.release(this.nodes);
                this.nodes = QuadtreeOptimized.arrayPool.acquire();
            } else {
                this.nodes = [];
            }
        }
        
        return allObjects;
    }
    
    /**
     * 清空
     */
    clear(): void {
        // 释放对象数组到池
        if (this.enableObjectPool) {
            QuadtreeOptimized.arrayPool.release(this.objects);
            this.objects = QuadtreeOptimized.arrayPool.acquire();
            this.stats.poolReleases++;
        } else {
            this.objects = [];
        }
        
        // 递归清空子节点
        for (let i = 0; i < this.nodes.length; i++) {
            if (this.nodes.length) {
                this.nodes[i].clear();
            }
        }
        
        if (this.enableObjectPool) {
            QuadtreeOptimized.arrayPool.release(this.nodes);
            this.nodes = QuadtreeOptimized.arrayPool.acquire();
            this.stats.poolReleases++;
        } else {
            this.nodes = [];
        }
        
        // 清空缓存和追踪
        if (this.level === 0) {
            this.queryCache.clear();
            this.objectTrackers.clear();
        }
    }
    
    // ========================================================================
    // 优化功能
    // ========================================================================
    
    /**
     * 追踪对象（用于增量更新）
     */
    private trackObject(obj: ObjectsType): void {
        if (!this.objectTrackers.has(obj)) {
            this.objectTrackers.set(obj, {
                object: obj,
                lastIndex: this.getIndex(obj),
                dirty: false
            });
        }
    }
    
    /**
     * 增量更新对象
     */
    private updateIncremental(obj: ObjectsType, fast: boolean): void {
        this.stats.incrementalUpdates++;
        
        const tracker = this.objectTrackers.get(obj);
        if (!tracker) {
            // 没有追踪记录，回退到常规更新
            this.remove(obj, fast);
            this.insert(obj);
            return;
        }
        
        const newIndex = this.getIndex(obj);
        
        // 检查是否改变了象限
        if (this.indexesEqual(tracker.lastIndex, newIndex)) {
            // 没有改变象限，无需重新插入
            tracker.lastIndex = newIndex;
            return;
        }
        
        // 改变了象限，需要重新插入
        this.remove(obj, fast);
        this.insert(obj);
        
        tracker.lastIndex = newIndex;
    }
    
    /**
     * 比较索引是否相等
     */
    private indexesEqual(a: number[], b: number[]): boolean {
        if (a.length !== b.length) return false;
        
        for (let i = 0; i < a.length; i++) {
            if (a[i] !== b[i]) return false;
        }
        
        return true;
    }
    
    /**
     * 获取缓存的查询结果
     */
    private getCachedQuery(obj: Rectangle|Circle|Line|Indexable): ObjectsType[] | null {
        const key = this.getCacheKey(obj);
        const cached = this.queryCache.get(key);
        
        if (!cached) return null;
        
        // 检查缓存是否过期
        const now = performance.now();
        if (now - cached.timestamp > this.cacheMaxAge) {
            this.queryCache.delete(key);
            return null;
        }
        
        return cached.results;
    }
    
    /**
     * 缓存查询结果
     */
    private cacheQuery(obj: Rectangle|Circle|Line|Indexable, results: ObjectsType[]): void {
        const key = this.getCacheKey(obj);
        
        this.queryCache.set(key, {
            bounds: this.getBounds(obj),
            results,
            timestamp: performance.now()
        });
        
        // 限制缓存大小
        if (this.queryCache.size > 1000) {
            // 删除最旧的条目
            const firstKey = this.queryCache.keys().next().value;
            if (firstKey !== undefined) {
                this.queryCache.delete(firstKey);
            }
        }
    }
    
    /**
     * 生成缓存键
     */
    private getCacheKey(obj: Rectangle|Circle|Line|Indexable): string {
        const bounds = this.getBounds(obj);
        return `${bounds.x}|${bounds.y}|${bounds.width}|${bounds.height}`;
    }
    
    /**
     * 获取对象边界
     */
    private getBounds(obj: Rectangle|Circle|Line|Indexable): NodeGeometry {
        if ('width' in obj && 'height' in obj) {
            // Rectangle
            return {
                x: obj.x,
                y: obj.y,
                width: (obj as any).width,
                height: (obj as any).height
            };
        } else if ('r' in obj) {
            // Circle
            const r = (obj as any).r;
            return {
                x: obj.x - r,
                y: obj.y - r,
                width: r * 2,
                height: r * 2
            };
        } else if ('x1' in obj) {
            // Line
            const line = obj as any;
            const minX = Math.min(line.x1, line.x2);
            const minY = Math.min(line.y1, line.y2);
            const maxX = Math.max(line.x1, line.x2);
            const maxY = Math.max(line.y1, line.y2);
            return {
                x: minX,
                y: minY,
                width: maxX - minX,
                height: maxY - minY
            };
        }
        
        // 默认
        return { x: 0, y: 0, width: 0, height: 0 };
    }
    
    /**
     * 失效缓存
     */
    private invalidateCache(): void {
        this.queryCache.clear();
    }
    
    // ========================================================================
    // 高级查询
    // ========================================================================
    
    /**
     * 范围查询（返回指定矩形区域内的所有对象）
     */
    queryRect(x: number, y: number, width: number, height: number): ObjectsType[] {
        const rect = {
            x, y, width, height,
            qtIndex: (node: NodeGeometry) => {
                const indexes: number[] = [];
                const centerX = node.x + node.width / 2;
                const centerY = node.y + node.height / 2;
                
                const startIsNorth = y < centerY;
                const startIsWest = x < centerX;
                const endIsEast = x + width > centerX;
                const endIsSouth = y + height > centerY;
                
                if (startIsNorth && endIsEast) indexes.push(0);
                if (startIsWest && startIsNorth) indexes.push(1);
                if (startIsWest && endIsSouth) indexes.push(2);
                if (endIsEast && endIsSouth) indexes.push(3);
                
                return indexes;
            }
        };
        
        return this.retrieve(rect as any);
    }
    
    /**
     * 圆形范围查询
     */
    queryCircle(x: number, y: number, radius: number): ObjectsType[] {
        const circle = {
            x, y, r: radius,
            qtIndex: (node: NodeGeometry) => {
                const indexes: number[] = [];
                const w2 = node.width / 2;
                const h2 = node.height / 2;
                const x2 = node.x + w2;
                const y2 = node.y + h2;
                
                const nodes = [
                    [x2, node.y],
                    [node.x, node.y],
                    [node.x, y2],
                    [x2, y2]
                ];
                
                for (let i = 0; i < nodes.length; i++) {
                    const deltaX = x - Math.max(nodes[i][0], Math.min(x, nodes[i][0] + w2));
                    const deltaY = y - Math.max(nodes[i][1], Math.min(y, nodes[i][1] + h2));
                    if ((deltaX * deltaX + deltaY * deltaY) < (radius * radius)) {
                        indexes.push(i);
                    }
                }
                
                return indexes;
            }
        };
        
        return this.retrieve(circle as any);
    }
    
    /**
     * K 近邻查询（返回距离指定点最近的 K 个对象）
     */
    queryKNearest(x: number, y: number, k: number): ObjectsType[] {
        // 先用较小半径查询
        let radius = 100;
        let results: ObjectsType[] = [];
        
        while (results.length < k && radius < Math.max(this.bounds.width, this.bounds.height)) {
            results = this.queryCircle(x, y, radius);
            radius *= 2;
        }
        
        // 计算距离并排序
        const withDistance = results.map(obj => {
            const bounds = this.getBounds(obj);
            const objX = bounds.x + bounds.width / 2;
            const objY = bounds.y + bounds.height / 2;
            const dist = Math.sqrt((x - objX) ** 2 + (y - objY) ** 2);
            return { obj, dist };
        });
        
        withDistance.sort((a, b) => a.dist - b.dist);
        
        return withDistance.slice(0, k).map(item => item.obj);
    }
    
    // ========================================================================
    // 统计和调试
    // ========================================================================
    
    /**
     * 获取统计信息
     */
    getStats() {
        return {
            ...this.stats,
            cacheSize: this.queryCache.size,
            trackedObjects: this.objectTrackers.size,
            cacheHitRate: this.stats.totalRetrieves > 0 
                ? (this.stats.cacheHits / this.stats.totalRetrieves * 100).toFixed(1) + '%'
                : '0%'
        };
    }
    
    /**
     * 重置统计信息
     */
    resetStats(): void {
        this.stats = {
            totalInserts: 0,
            totalRetrieves: 0,
            cacheHits: 0,
            cacheMisses: 0,
            poolAcquires: 0,
            poolReleases: 0,
            incrementalUpdates: 0
        };
    }
    
    /**
     * 打印统计信息
     */
    printStats(): void {
        const stats = this.getStats();
        
        Log.styled('━'.repeat(60), 'separator');
        Log.styled('📊 优化版四叉树统计', 'title');
        Log.styled('━'.repeat(60), 'separator');
        
        Log.performance.info('操作统计', {
            插入次数: stats.totalInserts,
            查询次数: stats.totalRetrieves,
            增量更新: stats.incrementalUpdates
        });
        
        Log.performance.info('缓存统计', {
            缓存命中: stats.cacheHits,
            缓存未命中: stats.cacheMisses,
            命中率: stats.cacheHitRate,
            缓存大小: stats.cacheSize
        });
        
        Log.performance.info('对象池统计', {
            获取次数: stats.poolAcquires,
            释放次数: stats.poolReleases,
            追踪对象: stats.trackedObjects
        });
        
        Log.styled('━'.repeat(60), 'separator');
    }
    
    /**
     * 销毁
     */
    destroy(): void {
        this.clear();
        this.queryCache.clear();
        this.objectTrackers.clear();
        
        // 清空对象池（仅根节点）
        if (this.level === 0) {
            QuadtreeOptimized.arrayPool.clear();
        }
    }
}

